package someTestExcemple.huaweiOd.greedyMethod;

//华为OD机试 - 选举拉票 - 贪心算法（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/146998456
import java.util.*;
public class CanvassingForTheElection {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取选民数目
        int n = scanner.nextInt();
        // 存储每个候选人的票数 key-候选人号码 value-票数
        Map<Integer, Integer> voteCount = new HashMap<>();
        // 存储每个候选人的花费列表   投给他的每张票改投给我的价值
        Map<Integer, List<Integer>> costList = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int candidate = scanner.nextInt();
            int cost = scanner.nextInt();
            // 统计每个候选人的票数
            voteCount.put(candidate, voteCount.getOrDefault(candidate, 0) + 1);
            // 将每个候选人对应的花费添加到列表中
            costList.computeIfAbsent(candidate, k -> new ArrayList<>()).add(cost);
        }
        // 先将除自己（0号候选人）外的其他候选人的花费列表排序
        for (Map.Entry<Integer, List<Integer>> entry : costList.entrySet()) {
            if (entry.getKey() != 0) {
                Collections.sort(entry.getValue()); //默认由小到大
            }
        }

        //，整体的时间复杂度由枚举目标票数部分主导，为O(n2logn)
        int minCost = Integer.MAX_VALUE;
        // 枚举自己需要达到的票数
        //至少要一票
        for (int targetVotes = voteCount.getOrDefault(0, 0) + 1; targetVotes <= n; targetVotes++) {
            int currentCost = 0;
            // 复制一份投票计数
            Map<Integer, Integer> tempVoteCount = new HashMap<>(voteCount);
            // 复制一份花费列表
            Map<Integer, List<Integer>> tempCostList = new HashMap<>();
            for (Map.Entry<Integer, List<Integer>> entry : costList.entrySet()) {
                tempCostList.put(entry.getKey(), new ArrayList<>(entry.getValue()));
            }
            // 计算需要从其他候选人那里拉来的票数
            int needVotes = targetVotes - voteCount.getOrDefault(0, 0);
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            // 先尝试从其他候选人那里拉票，使得他们的票数不超过目标票数 - 1
            for (Map.Entry<Integer, Integer> entry : tempVoteCount.entrySet()) {
                int candidate = entry.getKey();
                int votes = entry.getValue();
                if (candidate != 0) {
                    while (votes >= targetVotes) {
                        pq.add(tempCostList.get(candidate).remove(0));
                        votes--;
                        needVotes--;
                        currentCost += pq.poll();
                    }
                }
            }
            // 如果还需要拉票，从优先队列中选取花费最小的
            while (needVotes > 0) {
                for (Map.Entry<Integer, List<Integer>> entry : tempCostList.entrySet()) {
                    //这个候选人还有票
                    if (entry.getKey() != 0 && !entry.getValue().isEmpty()) {
                        pq.add(entry.getValue().get(0));
                    }
                }
                if (!pq.isEmpty()) {
                    currentCost += pq.poll();
                    needVotes--;
                }
            }
            // 更新最小花费
            minCost = Math.min(minCost, currentCost);
        }
        System.out.println(minCost);
        scanner.close();
    }


}
